Search Results

1. P. Kaski, A. Penttinen and J. Suomela, Coordinating Concurrent Transmissions: A Constant-Factor Approximation of Maximum Weight Independent Set in Local Conflict Graphs, in Proceedings of the 6th International Conference on AD-HOC Networks & Wireless, AdHoc-Now 2007, Lecture Notes in Computer Science, Volume 4686/2007, pp. 74-86, 2007, Morelia, Mexico (link)(bib)

   Abstract: We study the algorithmic problem of coordinating transmis- sions in a wireless network where radio interference constrains concur- rent transmissions on wireless links. We focus on pairwise conflicts be- tween the links; these can be described as a conflict graph. Associated with a conflict graph are two fundamental network coordination tasks: (a) finding a nonconflicting set of links with the maximum total weight, and (b) finding a link schedule with the minimum total length. Our work shows that two assumptions on the geometric structure of con- flict graphs suffice to achieve polynomial-time constant-factor approxi- mations: (i) bounded density of devices, and (ii) bounded range of inter- ference. We also show that these assumptions are not sufficient to obtain a polynomial-time approximation scheme for either coordination task.